#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
class Solution
{
    vector<int> vt;

public:
    // 权重前缀合 模拟出一条线 每个下标的权重为其中一段
    Solution(vector<int> &w) : vt(w)
    {
        for (int i = 1; i < vt.size(); i++)
        {
            vt[i] += vt[i - 1];
        }
    }
    // rand随机生成一个线段中的点,二分查找这个点属于哪一个段
    int pickIndex()
    {
        return lower_bound(vt.begin(), vt.end(), rand() % (vt.back()) + 1) - vt.begin();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */